<?php
/**
 * User: LRZ
 * Date: 2020/2/24
 * Time: 12:48
 */

/**
 *  20.有效括号
 *
 *  标签：栈、字符串
 *
 *  给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *  有效字符串需满足：
 *      左括号必须用相同类型的右括号闭合。
 *      左括号必须以正确的顺序闭合。
 *      注意空字符串可被认为是有效字符串。
 *
 *  示例 1:
 *      输入: "()"
 *      输出: true
 *
 *  示例 2:
 *      输入: "()[]{}"
 *      输出: true
 *
 *  示例 3:
 *      输入: "(]"
 *      输出: false
 *
 *  示例 4:
 *      输入: "([)]"
 *      输出: false
 *
 *  示例 5:
 *      输入: "{[]}"
 *      输出: true
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/valid-parentheses
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$s   = '()';
$res = isValid($s);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function isValid($s)
{
    $stack = [];
    $map   = [
        ')' => '(',
        ']' => '[',
        '}' => '{',
    ];
    $size  = strlen($s);
    if (($size > 0 && isset($map[$s[0]]))) {
        return false;
    }
    for ($i = 0; $i < $size; $i++) {
        if (isset($map[$s[$i]])) {
            $temp = array_pop($stack);
            if ($map[$s[$i]] !== $temp) {
                return false;
            }
        } else {
            $stack[] = $s[$i];
        }
    }
    return $stack ? false : true;
}